package 动态规划专项训练.动态规划训练2;

/**92.背包问题
 * @author zx
 * @create 2022-04-19 16:06
 */
public class LintCode92 {
    public int backPack(int m, int[] a) {
        int n = a.length;
        if(n == 0){
            return 0;
        }
        boolean[][] f = new boolean[n + 1][m + 1];
        f[0][0] = true;
        for(int j = 1;j <= m;j++){
            f[0][j] = false;
        }
        for(int i = 1;i <= n;i++){
            for(int j = 0;j <= m;j++){
                f[i][j] = f[i - 1][j];
                if(j >= a[i - 1]){
                    f[i][j] = f[i][j] || f[i - 1][j - a[i - 1]];
                }
            }
        }
        for(int i = m;i >= 0;i--){
            if(f[n][i]){
                return i;
            }
        }
        return 0;
    }
}
